package org.example;

import java.util.ArrayList;
import java.util.List;

public class Test3 {
    //leetcode 300 最长递增子序列 https://leetcode.cn/problems/longest-increasing-subsequence/description/

    /**
     * 因为这个题目只计算最长子序列的长度而不需要知道具体的内容，所以我们只需要知道递增序列的最后一个元素是啥就可以了
     * x长度的递增序列，我们只记录最后一个元素，然后遍历数组的时候，让这个元素分别和1，2，3...长度的递增序列的最后一个元素
     * 做比较，如果nums[i]大于最后一个元素，就说明nums[i]可以加在x长度的子序列的后面，就让nums[i]和x+1的子序列的最后一个
     * 元素进行比较，直到x长度的子序列不存在的时候，那么就将nums[i]的值记录在x+1长度上
     *
     * 简单来说就是记录，最长子序列的最后一个元素额值，然后判断nums[i]能插入到哪个位置
     * @param nums
     * @return
     */
    public int lengthOfLIS(int[] nums) {
        List<Integer> list = new ArrayList<>();
        list.add(nums[0]);
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] > list.get(list.size() - 1)) {
                list.add(nums[i]);
                continue;
            }
            int index = find(list,nums[i]);
            list.set(index,nums[i]);
        }
        return list.size();
    }

    private int find(List<Integer> list,int target) {
        int left = 0, right = list.size();
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (list.get(mid) < target) {
                left = mid + 1;
            }else {
                right = mid;
            }
        }
        return left;
    }
}
